package com.interview.javabase.algorithm;

import org.springframework.util.CollectionUtils;

import java.util.Arrays;
import java.util.List;

/**
 * @author: zsg
 * @description:
 * @date: 2019/8/17 16:27
 * @modified:
 */
public class HandWriteSingleCircleLinked {

    public static void main(String[] args) {
        LinkedNode head = createLinked(Arrays.asList(7, 8, 9, 10, 11, 12));
        printLinked(head);

        System.out.println();

        solutionJosephusProblem(head,1,3);
    }

    /**
     * 创建大量节点
     *
     * @param list
     * @return
     */
    public static LinkedNode createLinked(List<Integer> list) {
        LinkedNode head = null;
        LinkedNode temp = null;
        for (int i = 0; i < list.size(); i++) {
            LinkedNode linkedNode = new LinkedNode(list.get(i));
            if (temp != null) {
                temp.next = linkedNode;
            } else {
                head = linkedNode;
            }
            temp = linkedNode;
            linkedNode.next = head;
        }
        return head;
    }

    /**
     * 打印节点
     *
     * @param head
     */
    public static void printLinked(LinkedNode head) {

        LinkedNode temp = head;
        while (true) {
            System.out.print(temp.val + " ");
            if (temp.next == head){
                break;
            }
            temp = temp.next;
        }
    }


    /**
     * 计算链表的长度
     *
     * @param head
     * @return
     */
    public static int linkedLength(LinkedNode head) {
        LinkedNode temp = head;

        int length = 0;
        while (true) {
            length++;
            if (temp.next == head){
                break;
            }

            temp = temp.next;
        }

        return length;
    }

    /**
     * 约瑟夫问题
     * @param head
     * @param k 从第几个节点开始移动
     * @param m 每次移动几个节点
     */
    public static void  solutionJosephusProblem(LinkedNode head, int k, int m){

        // 计算有多少个节点
        int length = linkedLength(head);

        LinkedNode rear = head;

        // 先将rear移动到队尾
        while (true) {
            if (rear.next == head){
                break;
            }

            rear = rear.next;
        }

        // 将头结点指向开始移动的位置
        for (int i = 0; i < k - 1; i++) {
            head = head.next;
            rear = rear.next;
        }

        while (head != rear){

            // 每次移动m节点
            for (int i = 0; i < m -1; i++) {
                head = head.next;
                rear = rear.next;
            }

            // 删除 head
            System.out.println("当前出列的是 "+head.val);
            head = head.next;
            rear.next = head;
        }

        if (head == rear){
            System.out.println("当前出列的是 "+rear.val);
        }
    }

}
